11121. Основание -2

 

Рассмотрим систему счисления по основанию –2. Любое целое число n может быть однозначно представлено в виде: n = b0 + b1 * (–2) + b2 * (–2)2 + b3 * (–2)3 + … , где bi могут принимать только значения 0 и 1.

 

Вход. Первая строка содержит количество тестов N (не более 10000). Каждая следующая строка содержит число n в десятичной записи от –109 до 109.

 

Выход. Для каждого входного теста вывести его номер и представление числа n в системе счисления –2.

 

Пример входа

4

1

7

-2

0

 

Пример выхода

Case #1: 1

Case #2: 11011

Case #3: 10

Case #4: 0

 

 

РЕШЕНИЕ

системы счисления

 

Анализ алгоритма

Исходя из равенства n = b0 + b1 * (–2) + b2 * (–2)2 + b3 * (–2)3 + … следует, что число n делится на –2 только если оно четное, а число n – b0 должно делиться на –2. Если n четное, то положим b0 = 0 (если нечетное, то b0 = 1), делим n – b0 на –2, после чего рекурсивно продолжаем искать представление числа  в системе счисления по основанию –2.

Отдельно обрабатываем случай n = 0.

 

Пример

Пусть n = 6. Последовательно делим n на –2 с остатком:

6 / –2 = –3, остаток 0                Проверка: 6 = (–3) * (–2) + 0

–3 / –2 = 2, остаток 1                Проверка: –3 = 2 * (–2) + 1

2 / –2 = –1, остаток 0                Проверка: 2 = (–1) * (–2) + 0

–1 / –2 = 1, остаток 1                Проверка: –1 = 1 * (–2) + 1

Записав впереди 1 и остатки в обратном порядке, получим запись 11010, что составляет

 

Реализация алгоритма

Читаем количество тестов. Для каждого теста вводим значение n.

 

  scanf("%d",&tests);

  for(i = 0; i < tests; i++)

  {

    scanf("%d",&n);

 

Отдельно обрабатываем случай когда n = 0.

 

    if (!n)

    {

      printf("Case #%d: 0\n",i+1);

      continue;

    }

 

В строке s накапливаем цифры результата, инициализируем ее пустой строкой. Пока , записываем соответствующую цифру результата bi в строку s, вычитаем из n значение bi и делим разность n – bi на –2. То есть совершаем присваивание .

 

    s = "";

    while (n != 1)

    {

      if (n % 2) n -= 1, s += '1'; else s += '0';

      n /= -2;

    }

 

Добавим в конец строки 1, обернем ее и выведем на печать.

 

    s += '1';

    reverse(s.begin(),s.end());

    printf("Case #%d: %s\n",i+1,s.c_str());

  }